/*
 * search.cpp
 *
 *  Created on: Sep 18, 2011
 *      Author: ewertz
 */

#include "puzzleSettings.h"
#include <queue>
#include <ctime>
#include <sys/time.h>
#include <exception>
#include "nodeBroker.cpp"
using namespace std;


typedef node* nodePtr;

/*
 * This class is for implementing a priority Queue from the STL.
 */
class compareNode{
public:
	compareNode(){}
	bool operator()(const nodePtr & lhs, const nodePtr & rhs )const
	{
		return lhs->cost > rhs->cost;
	}
};
typedef priority_queue<nodePtr, vector<nodePtr>, compareNode> aliveCollection;






class search{

public:
	bool solution;
	node * root;
	node * active;

	nodeBroker * broker;

	node * upperbound;
	node * child;
	node n;


	aliveCollection alive;


	/*
	 * start our search
	 *
	 *
	 */
	void begin(node * rootNode, nodeBroker *NodeBroker, struct timeval &start){
		upperbound = NULL;  //stores best solution so far.
		solution = false;
		root = rootNode;
		broker = NodeBroker;
		active = root;
		bool stopSearching = false;


		alive.push(active); // seed the alive list with the root.


		if(findBestSolution){

			/*
			 * Uses upperbound to store current best solution.
			 */
			unsigned long count = 0;
			while(!alive.empty() && !stopSearching){
				count ++;
				if(count % 10000 == 0){ // check time every 10000 nodes;
					struct timeval stop;
					gettimeofday(&stop, NULL);

					double seconds  = stop.tv_sec  - start.tv_sec;
					double useconds = stop.tv_usec - start.tv_usec;

					double mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

					if (mtime > maxTime){
						stopSearching = true;
						continue; //exits loop for time expired.
					}
				}

				//active at this point is no longer needed, get new node to process from alive list.
				active = alive.top();
				alive.pop();

				//check to see if this is a goal.
				if(active->isGoal()){
					//check this new goal against upperbound, see if it is shorter
					if((upperbound == NULL) || active->cost_moves < upperbound->cost_moves){
						if(debugMajorStateChanges){ ///debug code
							struct timeval stop;
							gettimeofday(&stop, NULL);
							double seconds  = stop.tv_sec  - start.tv_sec;
							double useconds = stop.tv_usec - start.tv_usec;
							double mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

							if(upperbound == NULL)
								cout << "New Solution Found:  moves = " << active->cost_moves << ", milliseconds passed: " << mtime << endl;
							else
								cout << "Better Solution Found: moves = " << active->cost_moves << ", old solution: moves = " << upperbound->cost_moves << ", milliseconds passed: " << mtime << endl;
						}
						//upperbound needs to be replaced, so recycle the node.
						if(upperbound != NULL)
							broker->recycle(upperbound);
						upperbound = active;

						//continue checking the remaining nodes to see if any are a better solution.
						continue;
					} else {
						//Active is a goal but not better than upperbound, recycle the node and continue search
						broker->recycle(active);
						continue;
					}

				} else {
					//active node is not a solution, but it could be pruned by upperbound.
					if(upperbound != NULL){
						//Check active's number of moves + non-ranked distance from solution, prune if greater than upperbound's moves.
						unsigned int minDistance = active->cost_moves + active->minDist;
						if(minDistance > upperbound->cost_moves){
							//we know it is not worth investigating this node or its children, recycle it, and continue search
							broker->recycle(active);
							continue;
						}
					}
					//if we reach this point either there is no solution, or active could be a better solution, produce children.
					if (!(active->checkForCycles()) ){
						if(generateChildren() < 0){ //ran out of memory
							stopSearching = true;
							continue;
						}
					} else {
						//Recycle node for being a cycle.
						broker->recycle(active);
						if(debugCycles)
							cout << "cycle found, recycling node" << endl;
					}
				}
				// NO CODE GOES HERE, just continue while loop.
				continue;

			}

			if(upperbound == NULL) //upperbound is set by the last solution found
				cout << "no solution found" << endl;
			else
				upperbound->displayPath(); //this is the path to the upperBound, which is the current best solution.

		}
		else
		{
			/*
			 * This condition finds the first solution.
			 */


			while (solution == false && ! stopSearching){

				if(alive.empty()){
					cout << "solution not found" << endl;
					break;
				}
				active = alive.top();
				alive.pop();
		//	cout << "active moves = " << active -> cost_moves << " cost = " << active -> cost << endl;
				cout<<endl;
				if(debugAllNodes){
					cout<< "----------------------------------------------" << endl;
					cout << "ACTIVE" << endl;
					active->printNode();

				}

				solution = active->isGoal();
				if (solution && !timing){
						cout << "Goal Reached" << endl;
						active->displayPath();
				}
				else{
					if (!(active->checkForCycles()) ){
						if(generateChildren() < 0){ // memory error occurred generating children.
							stopSearching = true;
							continue; //exit for running out of memory.
						}
					}
					else{
						//Recycle node for being a cycle.
						broker->recycle(active);
						if(debugCycles)
							cout << "cycle found, recycling node" << endl;
					}
				}

		//		cin.get();
			}
		}

	}


	/**
	 * produces children of valid moves.
	 */
	int generateChildren(){

		// all direction  isValidMove prunes 2-cycles before they are created.
		for (int k=1;k<=4;k++)
			if(isValidMove(k,active)){
				child = broker->newNode();
				if(child == NULL)
					return -1;  //memory allocation error.
				child -> load(*active,k);
				addChild(k);
			}
		return 0; // no memory failure

	}

	void addChild( int direction){

		child->prevDirection = direction;
		child->parent = active;
		child->parent->references++;  //add reference counter to number of children pointing to parent.  parent is recycled when all children are recycled.
		if(debugAllNodes)
			child ->printNode();
		alive.push(child);

	}



	/**
	 * This just checks if the move can be made from this position and checks that the move is not reverse of the parents move.
	 *
	 * This is not complete cycle checking.
	 */

	bool isValidMove(int direction,node * active){
			 pos rowEmpty = active->board.emptyPos / width;
			 pos colEmpty = active->board.emptyPos % width;
			 switch(direction){
			 	case NORTH: { // move NORTH, fails if on edge (row = 0);
			 		if(rowEmpty == 0 || active->prevDirection == 2 )
			 			return false; //can't move up.
			 		return true;
			 	}
			 	case SOUTH: { // move SOUTH, fails if on edge (row = size-1);
			 		if(rowEmpty == width-1 || active->prevDirection == 1)
			 			return false; //can't move down.
			 		return true;
			 	}
			 	case EAST: { // move EAST, fails if on edge (col = size-1);
			 		if(colEmpty == width-1 || active->prevDirection == 4)
			 			return false; //can't move right.
			 		return true;
			 	}
			 	case WEST: { // move WEST, fails if on edge (col = 0);
			 		if(colEmpty == 0 || active->prevDirection == 3)
			 			return false; //can't move left.
			 		return true;
			 	}
			 	default: return false; // not a valid direction
			 }
		 }
};


